/**
 * 剑指 Offer 31. 栈的压入、弹出序列
 * https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
 */

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
function validateStackSequences(pushed, popped) {
  if (!pushed.length) {
    return true;
  }
  let nextToPush = 0;
  let nextToPop = 0;
  const stack = new Array(pushed.length).fill(0);
  let top = -1;
  while (nextToPush < pushed.length) {
    top += 1;
    stack[top] = pushed[nextToPush];
    nextToPush += 1;
    while (top >= 0 && stack[top] === popped[nextToPop]) {
      top -= 1;
      nextToPop += 1;
    }
  }
  return top < 0;
}

console.log(validateStackSequences([1, 2, 3, 4, 5], [4, 5, 3, 2, 1]) === true);
console.log(validateStackSequences([1, 2, 3, 4, 5], [4, 3, 5, 1, 2]) === false);
console.log(validateStackSequences([], []) === true);
